基本算法 | 数据结构与算法
yaotao
8月 20, 2017
【数据结构与算法】
- 简单的算法还是挺重要的，对于萌新来讲，最近的就是面试的时候就会用到·····
【希尔排序】
又叫递减增量排序算法
主要概念：步长 = N（总数）／2。
假设有一个总数为10的数据。 步长就为10/2 = 5，
第一次排序的时候将相隔5的两个数对比调整
第二次排序获取 5/2 = 2 步长 两两对换，直到步长为1
【快速排序】
快排的基本思想：1.找到一个基数，2.将全部小于这个基数的往前丢，大的往后，3.将得到的两个子集不断重复前面
1，2两步操作 直到子集的大小为1的时候结束
storeIndex：通俗的理解就是往前丢的数据有几个了
首先，把基准元素移到結尾（如果直接选择最后一个元素为基准元素，那就不用移动），然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1，表示下一个小于基准元素将要移动到的位置。循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置。所以最后将基准元素所在位置（这里是 right）与 storeIndex 所代表的的位置的元素交换位置。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。
【冒泡排序】
一个N个数据的数组
比较相邻两个数据 一直往后比较。
第一次排序N次完成就将最大的数据排到最后
下一次排序N-1次 将于下的最大数排后
直至完成
冒泡排序是比较简单的排序法，通过走访每一个数据。每一次排序将大的数据往后直到整个数据排序完成
例；
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |
第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |
第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
【插入排序】
时间复杂度：O（n^2)
空间复杂度：O（1）
将数据插入到排数组的合适位置
5 4 8 3 9 6
第一趟。取第一个数 5还是放在第一个位置 得到：5 4 8 3 9 6
第二趟。区第二个数4 和前面的数比较。 比5小。 放前面 得到：4 5 8 3 9 6
第三趟。 取第三个数8比较 ，放在5后面，即位置不动 得到：4 5 8 3 9 6
第四趟。 取第四个数3比较，比8小，比5小，比4小 得到：3 4 5 8 9 6
······· 得到：3 4 5 8 9 6
······· 得到：3 4 5 6 8 9